#define GRAPH_SPARSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
class SparseGraph
{
private:
    int n, m;
    bool isDirected;
    vector<vector<int>> g;
    /* data */
public:
    SparseGraph(int n, bool isDirected)
    {

        g=vector<vector<int>>(n,vector<int>());
        this->n = n;
        this->m=0;
        this->isDirected = isDirected;
    };
    ~SparseGraph(){
        
    };
    void addEdge(int v, int w)
    {
       
        g[v].push_back(w);
        if (v != w && !isDirected)
        {
            g[w].push_back(v);
         
            /* code */
        }
           m++;
    }
    bool hasEdge(int v, int w)
    {
        for (int i = 0; i < g[v].size(); i++)
        {
            if (g[v][i] == w)
            {
                return true;
                /* code */
            }
            return false;

            /* code */
        }
    }
    class adjIterator
    {
    private:
        SparseGraph &G;
        int v;
        int index;
        /* data */
    public:
        adjIterator(SparseGraph &graph, int v) : G(graph)
        {
            this->v = v;
            this->index = 0;
        };
        ~adjIterator(){

        };
        int begin()
        {
            index = 0;
            if (G.g[v].size())
            {
                return G.g[v][0];
                /* code */
            }
            return -1;
        }
        int next()
        {
            index++;
            if (index<G.g[v].size())
            {
                return G.g[v][index];
                /* code */
            }else{
                return -1;
            }
            
        }
        bool end()
        {
            return index>=G.g[v].size();
        }
    };
};

